package dp;

import java.util.HashMap;
import java.util.Map;

/**
 * @author wcj
 * @Date 2021/7/6 23:05
 * @Version 1.0
 */
public class LongestStr {

    public static void main(String[] args) {
        System.out.println(pt("ab"));
    }

    /**
     * 无重复字符的最长子串
     * 动态规划：
     * ①状态定义：dp[i]表示以第i个字符结尾的最长无重复字符子串
     * ②状态转移方程：i-map.getOrDefault(s.charAt(i))>dp[i-1]
     *
     * @param s
     * @return
     */
    public static int pt(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int res = 0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            int j = map.getOrDefault(s.charAt(i), -1);
            map.put(s.charAt(i), i);
            res = i - j > res ? res + 1 : i - j;
            max = Math.max(max, res);
        }
        return max;
    }
}
